package demo7;
import java.util.*;
public class Solution {
    //1.仅仅反转字母(模拟)
    public String reverseOnlyLetters(String s) {
        char[] arr = s.toCharArray();
        int left = 0;
        int right = arr.length - 1;
        while(left < right) {
            while(left < right && !(arr[left] >= 'a' && arr[left] <= 'z') &&
                    !(arr[left] >= 'A' && arr[left] <= 'Z')) {
                left++;
            }
            while(left < right && !(arr[right] >= 'a' && arr[right] <= 'z') &&
                    !(arr[right] >= 'A' && arr[right] <= 'Z')) {
                right--;
            }
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
        return String.valueOf(arr);
    }

    //2.重复的DNA序列(哈希表 + 切割子串)
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<>();
        //哈希表 + 切割子串(每隔10个字符串切割一次)
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i <= s.length() - 10; i++) {
            String str = s.substring(i, i + 10);
            if(!map.containsKey(str)) {
                map.put(str, 1);
            }else{
                map.put(str, map.get(str) + 1);
                if(map.get(str) == 2) {
                    ret.add(str);
                }
            }
        }
        return ret;
    }

    //2.重复的DNA序列(哈希表 + 切割子串)(优化)
/*    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<>();
        //哈希表 + 切割子串(每隔10个字符串切割一次)
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i <= s.length() - 10; i++) {
            String str = s.substring(i, i + 10);
            map.put(str, map.getOrDefault(str, 0) + 1);
            if(map.get(str) == 2) {
                ret.add(str);
            }
        }
        return ret;
    }*/
    //3.通过删除字母匹配到字典里最长单词(双指针)
    public String findLongestWord(String s, List<String> dictionary) {
        String ret = "";
        int count = 0;
        for(int i = 0; i < dictionary.size(); i++) {
            String str = dictionary.get(i);
            int strlen = str.length();
            //双指针
            int sp = 0;
            int dp = 0;
            while(sp < s.length() && dp < strlen) {
                if(s.charAt(sp) == str.charAt(dp)) {
                    sp++;
                    dp++;
                }else {
                    sp++;
                }
            }
            //可以是目标字符串
            if(dp == strlen && dp > count) {
                ret = str;
                count = dp;
                //需要比较字母序列
            }else if (dp == strlen && dp == count && ret.compareTo(str) > 0) {
                ret = str;
            }
        }
        return ret;
    }
    //剑指 Offer 67. 把字符串转换成整数
    public int strToInt(String str) {
        char[] chs = str.trim().toCharArray();
        if(chs.length == 0) {
            return 0;
        }
        int bord = Integer.MAX_VALUE / 10;
        int ret = 0;
        int j = 0;
        int sign = 1;
        if(chs[0] == '-') {
            sign = -1;//标志位为-1
            j = 1;
        }else if(chs[0] == '+') {
            j = 1;
        }
        for(int i = j; i < chs.length; i++) {
            char ch = chs[i];
            if(ch < '0' || ch > '9') {
                break;
            }
            if(ret > bord || ret == bord && chs[i] > '7') {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            ret = ret * 10 + chs[i] - '0';
        }
        return ret * sign;
    }
}
